﻿public class Solution
{
    private IList<IList<int>> result = new List<IList<int>>();
    private IList<int> path = new List<int>();
    
    public IList<IList<int>> SubsetsWithDup(int[] nums)
    {
        // 排序
        Array.Sort(nums);
        bool[] used = new bool[nums.Length];

        trackbacking(nums, 0, used);
        return result;
    }

    private void trackbacking(int[] nums, int start, bool[] used)
    {
        result.Add(new List<int>(path));
        
        if (start >= nums.Length) return;
        
        

        for (int i = start; i < nums.Length; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.Add(nums[i]);
            used[i] = true;
            trackbacking(nums, i + 1, used);
            used[i] = false;
            path.RemoveAt(path.Count - 1);
        }
    }

    public static void Main(string[] args)
    {
        int[] nums = [1, 2, 2];

        Solution solution = new Solution();
        IList<IList<int>> result = solution.SubsetsWithDup(nums);

        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}